package presums;

import java.util.HashMap;
import java.util.Map;

/**
 * @author pengfei.hpf
 * @date 2020/3/9
 * @verdion 1.0.0
 * 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
 *
 * 示例 1 :
 *
 * 输入:nums = [1,1,1], k = 2
 * 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
 * 说明 :
 *
 * 数组的长度为 [1, 20,000]。
 * 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
 * 通过次数17,723提交次数40,070
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/subarray-sum-equals-k
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class SubarraySum {
    /**
     * TODO: 考虑连续数重复出现的情况, 将出现过的和的次数记录下来, 每次前缀和减去目标后如果在map中已有,说明从之前那里到当前数的连续和就是目标值
     * */

    public int subarraySum(int[] nums, int k) {
        if(nums == null){
            return 0;
        }
        int sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int count = 0;
        for(int i = 0; i < nums.length; i ++){
            sum += nums[i];
            int sub = sum - k;
            if(map.containsKey(sub)){
                count += map.get(sub);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}
